おきらくＰｅｒｌプログラミング入門
～～めざせ Perl マスター～～
広井 誠
第１４回
○パズルの解法（その２）
前回はバックトラックを使って「騎士巡歴の問題」を解きました。今回はもう
一つの探索方法である、「幅優先探索」を使ってパズルを解いてみましょう。最
初に、経路の探索を例題にして、幅優先探索を説明します。
○幅優先探索
前回と同様に、下図に示す経路を使います。
Ｈ───Ｉ───Ｊ───Ｋ
│ │ ／│
│ │ ／ │
│ │／ │
Ｅ───Ｆ───Ｇ
│ ／│ │
│ ／ │ │
│／ │ │
Ａ───Ｂ───Ｃ───Ｄ
図 1 : 経路図の例
バックトラックによる探索では、一つの経路をできるだけ先へ延ばしていきま
すが、全ての経路について並行に探索を進めていく方法が「幅優先探索」です。
[A] ─┬─ [A,B] ─┬─ [A,B,C] ─┬─ [A,B,C,D] ─ 行き止まり
│ └─ [A,B,F] └─ [A,B,C,G]
│
├─ [A,F] ─┬─ [A,F,B] ・・・・・
│ ├─ [A,F,G]
│ ├─ [A,F,I]
│ ├─ [A,F,J] ─┬─ [A,F,J,G]
│ └─ [A,F,G] ├─ [A,F,J,I]
│ └─ [A,F,J,K] ─ GOAL
└─ (A E) ─┬─ [A,E,F]
└─ [A,E,H]
（出発点） （2 節点） （3 節点） （4 節点）
図 2 : 幅優先探索
まず、出発点 A から一つ進んだ経路(2 節点)を全て求めます。この場合は、
[A,B] [A,F] [A,E] の 3 つあり、これを全て記憶しておきます。次に、これら
の経路からひとつ延ばした経路(3 節点)を全て求めます。経路 [A,B] は [A,B,
C] と [A,B,F] へ延ばすことができますね。他の経路 [A,F] と [A,E] も同様に
延ばし、全ての経路を記憶します。後は、この作業をゴールに達するまで繰り返
します。バックトラックの縦形探索に対して、幅優先探索は「横形探索」とも呼
ばれます。
上図では、4 節点の経路 [A,F,J,K] でゴールに達していることがわかります。
このように幅優先探索では、最初に見つかった経路は最短距離(または最小手数)
となるのです。この性質は、全ての経路を並列に延ばしていく探索順序から考え
れば、当然のことといえるでしょう。この後も、探索を繰り返せば全ての経路を
求めることができます。
パズルなどの問題では、最小手数が解答の条件になることが多いので、その場
合は幅優先探索を使うことを考えてみるといいでしょう。ただし、探索を進める
にしたがって、記憶しておかなければならない経路の総数が爆発的に増加する、
つまりメモリを大量消費することに注意してください。上図の場合では、メモリ
を大量消費することはありませんが、問題によっては、マシンに搭載されている
メモリが不足するため、幅優先探索を実行できない場合もあるでしょう。したがっ
て、幅優先探索を使う場合は、メモリ消費量が少なくなるように工夫することが
重要です。
経路の管理ですが、「キュー(queue)」というデータ構造を使うと簡単にプロ
グラムできます。キューは待ち行列といわれるデータ構造です。たとえば、チケッ
トを買う場合窓口に長い列ができますが、それと同じだと考えてください。チケッ
トを買う時は、列の途中に割り込むことはできませんね。一番後ろに並んで順番
を待たなければいけません。列の先頭まで進むと、チケットを購入することがで
きるわけです。このように、要素を取り出す場合は列の先頭から行い、要素を追
加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先
出し(FIFO:first-in, first-out)」[*1]とも呼ばれます。
out in
---------------------------
<= A B C D E . . . Z <=
---------------------------
図 3 : キューの構造
Perl の場合、配列にデータをセットする時に push を使い、データを取り出
す時に shift を使うと、キューを実現することができます。逆に、unshift, pop
を使ってもかまいません。
note:
[*1] キューと対になるデータ構造が「スタック(stack)」です。スタックは後
から入れたデータから取り出されるので、後入れ先出し(LIFO:last-in,
first-out)と呼ばれます。Perl の場合、配列にデータをセットする時に
push を使い、データを取り出す時に pop を使うと、スタックを実現する
ことができます。
幅優先探索でのキューの動作は次のようになります。
(1) ───── QUEUE ──────
┌── [A]
│ ───────────────
│
└─→ キューからデータを取り出す
(2) ───── QUEUE ──────
←─┐
─────────────── │
│
[A] の経路を進め [A,B] ───┤
キューに追加する [A,F] ───┤
[A,E] ───┘
(3) ───── QUEUE ──────
┌── [A,B] [A,F] [A,E] ←─┐
│ ─────────────── │
│ │
└─→ [A,B] の経路を進めキューに追加 │
[A,B,C] [A,B,F] ────────┘
(4) ───── QUEUE ──────
┌── [A,F] [A,E] [A,B,C] [A,B,F] ←─┐
│ ─────────────── │
│ │
└─→ キューに経路がある間繰り返す ──┘
図 4 : 幅優先探索とキューの動作
最初は、(1) のように出発点をキューにセットしておきます。次に、キューか
ら経路を取り出し、(2) のように経路 [A] をひとつ延ばして、経路 [A,B] [A,
F] [A,E] を作り、それをキューに追加します。(3) では、経路 [A,B] を取り出
して、一つ延ばした経路 [A,B,C] と [A,B,F] をキューに追加します。後は、
キューに経路がある間、処理を繰り返せばいいわけです。
キューは先入れ先出し(FIFO)の性質を持つデータ構造なので、距離の短い経路
から順番に処理されるため、幅優先探索として機能するのです。
それではプログラムを作りましょう。経路は無名配列で表し、それをキューに
格納します。今回も隣接リストを使って経路図を表します。
List 1 : 隣接リスト
1 %adjacent = (
2 'A' => ['B', 'E', 'F'],
3 'B' => ['A', 'C', 'F'],
4 'C' => ['B', 'D', 'G'],
5 'D' => ['C'],
6 'E' => ['A', 'F', 'H'],
7 'F' => ['A', 'B', 'E', 'G', 'I', 'J'],
8 'G' => ['C', 'F', 'J'],
9 'H' => ['E', 'I'],
10 'I' => ['F', 'H', 'J'],
11 'J' => ['G', 'I', 'K'],
12 'K' => ['J']
13 );
探索を行う関数 search は次のようになります。
List 2 : 幅優先探索
1 sub search {
2 my ($start, $end) = @_;
3 my @queue = ();
4 push( @queue, [$start] );
5 while( @queue > 0 ){
6 my $path = shift( @queue );
7 my $postion = $path->[$#$path];
8 foreach $next ( @{ $adjacent{$postion} } ){
9 if( !grep( /$next/, @$path ) ){
10 my $new_path = [ @$path ];
11 push( @$new_path, $next );
12 if( $next eq $end ){
13 print "@$new_path\n";
14 } else {
15 push( @queue, $new_path );
16 }
17 }
18 }
19 }
20 }
A から K までの経路を探索する場合、search を次のように呼び出します。
&search( 'A', 'K' );
キューは局所変数 @queue として定義し、スタート地点のみの経路 [$start] で
初期化します。6 行目で、shift でキューから経路を取り出し、7 行目で経路の
最後にある頂点を取り出し $postion にセットします。8 行目からの foreach
で、隣接リストから次へ進む頂点 $next を選びます。この時、$next が経路
$path に含まれていないことを確認します。頂点は文字で表しているので、grep
を使えば簡単にチェックできます。
経路を延ばす時は、$path に直接追加するのではなく、$path をコピーした
$new_path に対して行います。$path から複数の経路を作ることになるので、元
になる $path を書き換えてはいけません。12 行目で、$next が $end と等しい
のであれば、経路が完成したので print で表示します。そうでなければ、新し
い経路をキューに追加します。
それでは、プログラムを実行してみます。
実行結果
A F J K
A F G J K
A F I J K
A E F J K
A B F J K
A B F G J K
A B F I J K
A B C G J K
A E H I J K
A E F G J K
A E F I J K
A F B C G J K
A F E H I J K
A E H I F J K
A B C G F J K
A B F E H I J K
A B C G F I J K
A E H I F G J K
A E F B C G J K
A B C G F E H I J K
A E H I F B C G J K
結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる
経路が最長となります。当然ですが、経路の総数は 21 通りとなります。
○８パズル
次は、幅優先探索を使って実際にパズルを解いてみましょう。最短手数を求め
る問題として「８パズル」を取り上げます。
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│１│５│２│ │１│２│３│ │０│１│２│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│４│８│３│ ──→ │４│５│６│ │３│４│５│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│７│６│ │ │７│８│ │ │６│７│８│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
最初の配置 完成図 座標
図 5 : ８パズル
ようするに「１５パズル」の盤を小さくしたものです。完成図までの最小手数
を求めることにします。８パズルの局面は、空白の位置がどこにあってもよいと
すると、9! = 362880 通りあります。ただし、参考文献[3]によると、「適当な
二つの駒をつまみ上げて交換する動作を偶数回やった局面にしか移行できない」
ことが証明されているそうです。たとえば、完成図の 7 と 8 を入れ換えただけ
の配置は、交換が奇数回のため完成図に到達することができない、つまり解くこ
とができないのです。しがって、解ける局面は全部で 9! / 2 = 181440 個とな
ります。ちなみに、15 パズルの場合は 16! / 2 通り（約 10 の 13 乗）と局面
数がとても多く、幅優先探索で解くのは困難です。
局面は文字列で表現することにします。こうすると、同じ局面かチェックする
処理にハッシュを使うことができます。空白を 0 で表すと、最初の配置は
"152483760" で、完成図は "123456780" となります。駒の移動は、0 と隣接す
る数字を交換することで行います。これは文字列の置換で処理することができま
す。
最初に 0 の位置を求めます。文字列の中から文字を探すには関数 index を使
います。
index 文字列 部分文字列 [位置]
文字列の先頭から部分文字列を探し、最初に見つけた位置を返します。見つから
ない場合は -1 を返します。位置を指定すると、その位置から検索を開始します。
この他に関数 rindex があり、これは最後に現れた部分文字列の位置を返します。
次に、そこに隣接している位置を求めます。これは隣接リストを使うと簡単に
求めることができます。
List 3 : 隣接リスト
1 @adjacent = (
2 [1, 3], # 0
3 [0, 4, 2], # 1
4 [1, 5], # 2
5 [0, 4, 6], # 3
6 [1, 3, 5, 7], # 4
7 [2, 4, 8], # 5
8 [3, 7], # 6
9 [4, 6, 8], # 7
10 [5, 7] # 8
11 );
それから、その位置にある数字を取り出します。これは substr を使えばいい
ですね。この数字と 0 を交換するには、次のように文字列の置換を行えば実現
できます。
s/([0$n])(.*)([0$n])/$3$2$1/
数字を $n とすると、0 か $n から始まり、0 か $n で終わる部分文字列を探し
ます。そして、その最初の文字と最後の文字を交換すればいいわけです。正規表
現には () を使っているので、最初の文字は $1 に、間の文字列は $2 に、最後
の文字は $3 に格納されます。置換部分で、$1 と $3 をひっくり返して $3$2$1
とすれば、0 と $n を交換することができます。今回は文字列の置換を使いまし
たが、他にも方法があると思います。興味のある方は考えてみてください。
今度は移動手順の管理を考えましょう。経路の探索のように、局面の状態を配
列に格納して手順を表してもいいのですが、最短手数を求めるだけであれば、全
ての手順を記憶しておく必要はありません。n 手目の移動で作られた局面が、n
手目以前の局面で出現しているのであれば、n 手より短い手数で到達する移動手
順があるはずです。したがって、この n 手の手順を記憶しておく必要はないの
です。局面は単純な配列に格納し、番号で管理することにします。
@state @prev_state @move_start
------------- ------------- -------------
0 : 152483760 -1 0
1 : 152480763 0 1
2 : 152483706 0 3
3 : 150482763 1 7
4 : 152408763 1
5 : 152403786 2
6 : 152483076 2
図 6 : 手順の管理
局面は大域変数 @state に格納します。そして、その一つ前の局面の番号を大
域変数 @prev_state に格納します。@prev_state をたどることで、移動手順を
再現することができます。
i 手目の局面は、i - 1 手目の局面から駒を動かして作ります。1 手前の局面
を求めるため、大域変数 @move_start に n 手目の移動で作成された局面が始ま
る番号を格納します。
具体的に説明しましょう。上図を見てください。最初の配置を $state[0] に
セットします。$prev_state[0] には終端を表すため -1 をセットします。そし
て、$move_start[0] には 0 をセットし、1 手目の局面は番号 1 から始まるの
で $move_start[1] には 1 をセットします。次に、駒を移動して 1 手目の局面
を生成します。動かせる駒は 2 つしかないので、生成される局面は 2 つとなり
ます。それぞれ、$state[1] と $state[2] にセットし、$prev_state[1] と
$prev_state[2] には元の局面番号 0 をセットします。2 手目の局面は番号 3
から始まるので $move_state[2] には 3 をセットします。
3 手目の局面は 2 手目の局面から生成します。まず、番号 1 の局面の駒を動
かして新しい局面を作り、次に 番号 2 の局面の駒を動かします。この場合、全
部で 6 通りの局面が作られますが、そのうちの 2 つは最初の局面と同じになる
ので、新しい局面は 4 通りとなります。したがって、4 手目の局面は番号 7 か
ら始まり、$move_start[4] には 7 がセットされます。後は、完成図に到達する
まで処理を繰り返せばいいわけです。
それではプログラムを作りましょう。最初に大域変数を定義します。
List 4 : 大域変数定義
1 $end_state = "123456780";
2 @state = ();
3 @move_start = ();
4 @prev_state = ();
5 %check_state = ();
$end_state には完成図をセットします。後は、使用する配列を空に初期化して
いるだけです。%check_state は同一局面をチェックするためのハッシュです。
探索を行う関数 search は次のようになります。
List 5 : 探索
1 sub search {
2 my $move = 1;
3 my $count = 1;
4 $state[0] = shift;
5 $move_start[0] = 0;
6 $prev_state[0] = -1;
7 $check_state{$state[0]} = 1;
8
9 while( $count > $move_start[$move - 1] ){
10 my $i = $move_start[$move - 1];
11 print STDERR "$move 手の検索・・・\n\n";
12 $move_start[$move] = $count;
13 for( ; $i < $move_start[$move]; $i++ ){
14 my $zp = index( $state[$i], '0' );
15 foreach $np ( @{ $adjacent[$zp] } ){
16 my $c = substr( $state[$i], $np, 1 );
17 my $ns = $state[$i];
18 $ns =~ s/([0$c])(.*)([0$c])/$3$2$1/;
19 if( $end_state eq $ns ){
20 &print_history( $i );
21 return;
22 } elsif( !$check_state{$ns} ){
23 $state[$count] = $ns;
24 $prev_state[$count++] = $i;
25 $check_state{$ns} = 1;
26 }
27 }
28 }
29 $move++;
30 }
31 }
関数 search には引数として最初の局面を渡します。$move は手数を表し、
$count は生成した局面の数を表します。$state[0] には最初の局面をセットし、
$prev_state[0] には -1 を、$move_start[0] には 0 をセットします。それか
らハッシュ $check_state{$ns} を 1 にセットします。
9 行目の while ループで、新しい局面を生成できる間は処理を繰り返します。
もっとも、最初の局面に間違いがなければ、解は必ず見つかるはずです。
$move 手目の局面を生成するには、$move - 1 手目の局面を求めなければいけ
ません。まず、$move 手目の開始番号を $move_start[$move] にセットします。
それから 13 行目の for 文で、1 手前の局面を取り出し、駒を動かして新しい
局面を作ります。
新しい局面は変数 $ns にセットされます。この時 17 行目で、1 手前の局面
をコピーすることに注意してください。一つの局面から複数の局面が生成される
ので、元の局面を書き換えては正常に動作しません。また、手順の履歴も壊れて
しまいます。
19 行目で、新しい局面 $ns と $end_state が等しいのであれば、８パズルを
解くことができました。print_history で移動手順を表示します。そうでなけれ
ば、ハッシュ %check_state をチェックして同じ局面がないことを確かめ、デー
タを大域変数にセットします。
$move 手で移動できる局面を全てチェックしたら、29 行目で $move の値を
+1 して次の局面をチェックします。
次は手順を表示する関数 print_history を作ります。
List 6 : 手順を逆順で表示
1 sub print_history {
2 my $n = shift;
3 print_state( $end_state );
4 while( $n != -1 ){
5 my $s = $state[$n];
6 &print_state( $state[$n] );
7 $n = $prev_state[$n];
8 }
9 }
print_history は手順を逆に表示します。「逆は嫌だ」という方は改造してく
ださいね。@prev_state をたどり局面を表示します。@prev_state の値が -1 に
なると終了します。局面を表示する print_state は簡単なので説明は省略しま
す。
それでは実行してみましょう。
&search( "152483760" );
実行結果
123
456
780
123
450
786
120
453
786
102
453
786
152
403
786
152
483
706
152
483
760
6 手で解くことができました。X68030[25MHz] で実行した場合、10 手以下で
は高速に解くことができますが、10 手を越えると探索に時間がかかるようにな
ります。そこで、Ｃ言語でプログラムを作ってみました。同一局面のチェックに
は「二分探索木」というアルゴリズムを使っています。ただし、約 5 M byte の
メモリを必要とするので、実行にはご注意くださいませ。
Ｃ言語版の場合、参考文献[3]に掲載されていた一番難しい問題を与えると、
X68030[25MHz] で約 5 分かかります。その時の手数は 31 手、30 手までの局面
数は181438 個になります。ちなみに、[3]には局面を 0 から 362880 - 1 (= 9!
- 1) までの数値に変換する方法が紹介されています。この方法を使うと、少な
いメモリでも８パズルを解くことができるようです。
○ナンバープレース
この他に、ナンバープレースの解法プログラムを Perl で作りました。アルゴ
リズムは Lisp 入門講座の番外編(電脳倶楽部 Vol.137)で作成したプログラムと
ほぼ同じなので、説明は割愛いたします。ただし、バックトラックの検索で再帰
が深くなると、Perl 5 ではバスエラーが発生するので、再帰を「繰り返し」に
変換しています。関数 search が再帰による探索で、それを繰り返しに変換した
ものが search_1 です。興味のある方はソースファイル(numplace.pl)を読んで
みてください。
それから Perl の場合、解くまでに少々時間がかかるようなので、解を一つ発
見したら終了するようにプログラムしています。全解探索を行いたい場合は改造
してください。
○次回は？
いよいよ次回から、Perl 5 最大の特徴である「オブジェクト指向」の説明に
入ります。お楽しみに。
―参考文献―
[1] Larry Wall, Tom Christiansen, Randal L. Schwartz 共著「プログラミン
グＰｅｒｌ」改訂版 オライリー・ジャパン 1997
[2] 増井俊之 著 「Ｐｅｒｌ書法」アスキー 1993
[3] 吉柄貴樹,三木太郎,橋本哲 特集「コンピュータパズルへの招待」
C MAGAZINE 1996 年 2 月号 ソフトバンク
（ＥＯＦ）